package leetcode.code0085;

import java.util.Stack;

/**
 *
 * 执行用时：8 ms, 在所有 Java 提交中击败了58.32%的用户
 *
 * 内存消耗：41.6 MB, 在所有 Java 提交中击败了28.99%的用户
 *
 * 通过测试用例：71 / 71
 *
 * @author CaoYu
 * @date 2021年11月26日
 * @description
 */
public class Solution1 extends Solution85 {

	@Override
	public int maximalRectangle(char[][] matrix) {
		if (matrix == null) {
			return 0;
		}
		int rowSize = matrix.length;
		if (rowSize == 0) {
			return 0;
		}
		int colSize = matrix[0].length;
		if (colSize == 0) {
			return 0;
		}
		int[] line = new int[colSize];
		int max = 0;
		for (int i = 0; i < rowSize; i++) {
			for (int j = 0; j < colSize; j++) {
				line[j] += matrix[i][j] == '0' ? -line[j] : matrix[i][j] - '0';
			}
			max = Math.max(max, this.f(line, colSize));
		}
		return max;
	}

	private int f(int[] line, int colSize) {
		int ans = 0;
		Stack<Integer> s = new Stack<>();
		for (int i = 0; i < colSize; i++) {
			if (!s.isEmpty() && line[s.peek()] >= line[i]) {
				int right = s.peek();
				while (!s.isEmpty() && line[s.peek()] >= line[i]) {
					int index = s.pop();
					int left = s.isEmpty() ? -1 : s.peek();
					ans = Math.max(ans, (right - left) * line[index]);
				}
			}
			s.add(i);
		}
		int right = s.isEmpty() ? 0 : s.peek();
		while (!s.isEmpty()) {
			int index = s.pop();
			int left = s.isEmpty() ? -1 : s.peek();
			ans = Math.max(ans, (right - left) * line[index]);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
